YES 1.05
H-Termination proof of /home/matraf/haskell/eval_FullyBlown_Fast/empty.hs
H-Termination of the given Haskell-Program with start terms could successfully be proven:
↳ HASKELL
↳ BR
mainModule Main
| ((inRange :: Ix a => (a,a) -> a -> Bool) :: Ix a => (a,a) -> a -> Bool) |
module Main where
Replaced joker patterns by fresh variables and removed binding patterns.
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
mainModule Main
| ((inRange :: Ix a => (a,a) -> a -> Bool) :: Ix a => (a,a) -> a -> Bool) |
module Main where
Cond Reductions:
The following Function with conditions
compare | x y |
| | x == y | |
| | x <= y | |
| | otherwise | |
|
is transformed to
compare | x y | = compare3 x y |
compare1 | x y True | = LT |
compare1 | x y False | = compare0 x y otherwise |
compare2 | x y True | = EQ |
compare2 | x y False | = compare1 x y (x <= y) |
compare3 | x y | = compare2 x y (x == y) |
The following Function with conditions
is transformed to
undefined0 | True | = undefined |
undefined1 | | = undefined0 False |
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ LetRed
mainModule Main
| ((inRange :: Ix a => (a,a) -> a -> Bool) :: Ix a => (a,a) -> a -> Bool) |
module Main where
Let/Where Reductions:
The bindings of the following Let/Where expression
fromEnum c <= i && i <= fromEnum c' |
where | |
are unpacked to the following functions on top level
inRangeI | vx | = fromEnum vx |
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ LetRed
↳ HASKELL
↳ Narrow
mainModule Main
| (inRange :: Ix a => (a,a) -> a -> Bool) |
module Main where
Haskell To QDPs
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ LetRed
↳ HASKELL
↳ Narrow
↳ AND
↳ QDP
↳ QDPSizeChangeProof
↳ QDP
Q DP problem:
The TRS P consists of the following rules:
new_not(Succ(vy4000), Succ(vy31000)) → new_not(vy4000, vy31000)
R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs:
- new_not(Succ(vy4000), Succ(vy31000)) → new_not(vy4000, vy31000)
The graph contains the following edges 1 > 1, 2 > 2
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ LetRed
↳ HASKELL
↳ Narrow
↳ AND
↳ QDP
↳ QDP
↳ QDPSizeChangeProof
Q DP problem:
The TRS P consists of the following rules:
new_inRange(@2(@3(vy300, vy301, vy302), @3(vy310, vy311, vy312)), @3(vy40, vy41, vy42), bh, bd, app(app(app(ty_@3, cf), cg), da)) → new_inRange(@2(vy302, vy312), vy42, cf, cg, da)
new_inRange(@2(@3(vy300, vy301, vy302), @3(vy310, vy311, vy312)), @3(vy40, vy41, vy42), app(app(app(ty_@3, ba), bb), bc), bd, be) → new_inRange(@2(vy300, vy310), vy40, ba, bb, bc)
new_inRange(@2(@3(vy300, vy301, vy302), @3(vy310, vy311, vy312)), @3(vy40, vy41, vy42), bh, app(app(app(ty_@3, ca), cb), cc), be) → new_inRange(@2(vy301, vy311), vy41, ca, cb, cc)
new_inRange0(@2(@2(vy300, vy301), @2(vy310, vy311)), @2(vy40, vy41), eb, app(app(ty_@2, ef), eg)) → new_inRange0(@2(vy301, vy311), vy41, ef, eg)
new_inRange0(@2(@2(vy300, vy301), @2(vy310, vy311)), @2(vy40, vy41), eb, app(app(app(ty_@3, ec), ed), ee)) → new_inRange(@2(vy301, vy311), vy41, ec, ed, ee)
new_inRange(@2(@3(vy300, vy301, vy302), @3(vy310, vy311, vy312)), @3(vy40, vy41, vy42), bh, bd, app(app(ty_@2, db), dc)) → new_inRange0(@2(vy302, vy312), vy42, db, dc)
new_inRange(@2(@3(vy300, vy301, vy302), @3(vy310, vy311, vy312)), @3(vy40, vy41, vy42), bh, app(app(ty_@2, cd), ce), be) → new_inRange0(@2(vy301, vy311), vy41, cd, ce)
new_inRange(@2(@3(vy300, vy301, vy302), @3(vy310, vy311, vy312)), @3(vy40, vy41, vy42), app(app(ty_@2, bf), bg), bd, be) → new_inRange0(@2(vy300, vy310), vy40, bf, bg)
new_inRange0(@2(@2(vy300, vy301), @2(vy310, vy311)), @2(vy40, vy41), app(app(ty_@2, dh), ea), dg) → new_inRange0(@2(vy300, vy310), vy40, dh, ea)
new_inRange0(@2(@2(vy300, vy301), @2(vy310, vy311)), @2(vy40, vy41), app(app(app(ty_@3, dd), de), df), dg) → new_inRange(@2(vy300, vy310), vy40, dd, de, df)
R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs:
- new_inRange(@2(@3(vy300, vy301, vy302), @3(vy310, vy311, vy312)), @3(vy40, vy41, vy42), bh, bd, app(app(app(ty_@3, cf), cg), da)) → new_inRange(@2(vy302, vy312), vy42, cf, cg, da)
The graph contains the following edges 2 > 2, 5 > 3, 5 > 4, 5 > 5
- new_inRange(@2(@3(vy300, vy301, vy302), @3(vy310, vy311, vy312)), @3(vy40, vy41, vy42), bh, app(app(app(ty_@3, ca), cb), cc), be) → new_inRange(@2(vy301, vy311), vy41, ca, cb, cc)
The graph contains the following edges 2 > 2, 4 > 3, 4 > 4, 4 > 5
- new_inRange(@2(@3(vy300, vy301, vy302), @3(vy310, vy311, vy312)), @3(vy40, vy41, vy42), app(app(app(ty_@3, ba), bb), bc), bd, be) → new_inRange(@2(vy300, vy310), vy40, ba, bb, bc)
The graph contains the following edges 2 > 2, 3 > 3, 3 > 4, 3 > 5
- new_inRange(@2(@3(vy300, vy301, vy302), @3(vy310, vy311, vy312)), @3(vy40, vy41, vy42), bh, bd, app(app(ty_@2, db), dc)) → new_inRange0(@2(vy302, vy312), vy42, db, dc)
The graph contains the following edges 2 > 2, 5 > 3, 5 > 4
- new_inRange(@2(@3(vy300, vy301, vy302), @3(vy310, vy311, vy312)), @3(vy40, vy41, vy42), bh, app(app(ty_@2, cd), ce), be) → new_inRange0(@2(vy301, vy311), vy41, cd, ce)
The graph contains the following edges 2 > 2, 4 > 3, 4 > 4
- new_inRange(@2(@3(vy300, vy301, vy302), @3(vy310, vy311, vy312)), @3(vy40, vy41, vy42), app(app(ty_@2, bf), bg), bd, be) → new_inRange0(@2(vy300, vy310), vy40, bf, bg)
The graph contains the following edges 2 > 2, 3 > 3, 3 > 4
- new_inRange0(@2(@2(vy300, vy301), @2(vy310, vy311)), @2(vy40, vy41), eb, app(app(app(ty_@3, ec), ed), ee)) → new_inRange(@2(vy301, vy311), vy41, ec, ed, ee)
The graph contains the following edges 2 > 2, 4 > 3, 4 > 4, 4 > 5
- new_inRange0(@2(@2(vy300, vy301), @2(vy310, vy311)), @2(vy40, vy41), app(app(app(ty_@3, dd), de), df), dg) → new_inRange(@2(vy300, vy310), vy40, dd, de, df)
The graph contains the following edges 2 > 2, 3 > 3, 3 > 4, 3 > 5
- new_inRange0(@2(@2(vy300, vy301), @2(vy310, vy311)), @2(vy40, vy41), eb, app(app(ty_@2, ef), eg)) → new_inRange0(@2(vy301, vy311), vy41, ef, eg)
The graph contains the following edges 2 > 2, 4 > 3, 4 > 4
- new_inRange0(@2(@2(vy300, vy301), @2(vy310, vy311)), @2(vy40, vy41), app(app(ty_@2, dh), ea), dg) → new_inRange0(@2(vy300, vy310), vy40, dh, ea)
The graph contains the following edges 2 > 2, 3 > 3, 3 > 4